#include<iostream>
#include"AvlTree.h"
#include<algorithm>
#include<vector>
#include<ctime>
using namespace std;

void test()
{
  vector<int> arr;
  arr.push_back(3);
  arr.push_back(7);
  arr.push_back(9);
  arr.push_back(6);
  arr.push_back(-4);
  arr.push_back(0);
  arr.push_back(12);
  arr.push_back(-6);
  arr.push_back(8);
  arr.push_back(1);
  arr.push_back(11);
  
  AvlTree<int> tree;
  for(int i=0 ; i< arr.size() ; i++ )
    {
      tree.insert(arr[i]);
    }
    tree.printrange(-2 , 10.1);
    tree.printrange(99 , 1000);
    tree.printrange(5,-2);
  
};


void test1( vector<int> & arr3)
{
  // O(K + log(n))
   AvlTree<int> tree1;
  for(int i=0 ; i< arr3.size() ; i++ )
    {
      tree1.insert(arr3[i]);
    }
    clock_t start1, finish1;

    
    start1 = clock();
    tree1.printrange(400 , 401);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;

    start1 = clock();
    tree1.printrange(400 , 410);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;

    start1 = clock();
    tree1.printrange(400 , 500);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;
    
}



void test2( vector<int> & arr6)
{
  // O(K + log(n))
   AvlTree<int> tree1;
  for(int i=0 ; i< arr6.size() ; i++ )
    {
      tree1.insert(arr6[i]);
    }
    clock_t start1, finish1;

    
    start1 = clock();
    tree1.printrange(400 , 401);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;

    
    start1 = clock();
    tree1.printrange(400 , 410);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;

    
    start1 = clock();
    tree1.printrange(400 , 500);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;

    
     start1 = clock();
    tree1.printrange(4000 , 5000);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;

     start1 = clock();
    tree1.printrange(40000 , 50000);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;
    
}




void test3( vector<int> & arr8)
{
  // O(K + log(n))
   AvlTree<int> tree1;
  for(int i=0 ; i< arr8.size() ; i++ )
    {
      tree1.insert(arr8[i]);
    }
    clock_t start1, finish1;


    
    start1 = clock();
    tree1.printrange(400 , 401);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;

    
    start1 = clock();
    tree1.printrange(400 , 410);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;

    
    start1 = clock();
    tree1.printrange(400 , 500);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;

    
     start1 = clock();
    tree1.printrange(4000 , 5000);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;

    
     start1 = clock();
    tree1.printrange(40000 , 50000);
    finish1 = clock();
    cout <<endl<<"运行时间为:" << double(finish1 - start1) / CLOCKS_PER_SEC <<"秒" << endl;
    
    
}








int main()
{

  vector<int> arr3;
  for(int j=0 ;j< 1000 ; j++) //10^3
    {
      arr3.push_back(j);
    }
  random_shuffle(arr3.begin(),arr3.end());

  
  vector<int> arr6;
  for(int i=0 ;i< 1000*1000 ; i++) //10^6
    {
      arr6.push_back(i);
    }
  random_shuffle(arr6.begin(),arr6.end());

  
  vector<int> arr8;
  for(int k=0 ;k< 1000*1000*100 ; k++) //10^8
    {
      arr8.push_back(k);
    }
  random_shuffle(arr8.begin(),arr8.end());


  
  //  test();
  // test1(arr3);
  // test2(arr6);
   test3(arr8);
 

  return 0;
};
